package zcy.sort;

/**
 * 归并排序
 * 时间复杂度 O(n*logN)
 * 额外空间复杂度
 */
public class MergeSort {

    public static void process(int[] arr,int l,int r){ //请让arr从L到R上有序
        if (l == r){
            return;
        }
        int mid = (l+r)/2;
        process(arr,l,mid);
        process(arr,mid+1,r);
        merge(arr,l,mid,r);//左侧有序和右侧有序之后 让整体有序 merge过程没有调用递归
    }

    private static void merge(int[] arr, int l, int mid, int r) {
        int[] help = new int[r-l+1];
        int i=0; //给help 开辟一个空间和坐标
        int p1 = l;
        int p2= mid+1;
        while (p1 <= mid && p2 < r){ // 都不越界的时候 怎么merge
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2]++; //咱俩都不越界的时候  谁小copy谁
        }
        //下面两个while实际只能中一个
        while (p1 <= mid){
            help[i++] = arr[p1++];
        }
        while (p1 <= r){
            help[i++] = arr[p2++];
        }
        //把help的东西 copy到原数组中
        for (int k =0 ;k< help.length;k++){
            arr[l+k] = help[k];
        }
    }

}
